Journal of Advances in Computer Research
Volume:14 Issue: 2, Summer 2023

Clustering is an essential technique for analyzing unlabeled data. In the past few years, population-based meta-heuristic algorithms have been effectively used to solve optimization problems including data clustering. In this paper, a new model based on the combination of Search and Rescue Optimization Algorithm (SAR) with African Vulture Optimization Algorithm (AVOA) named Improved K-Means Search and Rescue with African Vulture Optimization Algorithm (IKM-SARAVOA) is proposed. Two common obstacles in achieving optimal clustering, i.e., premature convergence and getting stuck in local optima can be challenging for the complex clustering problem. In the IKM-SARAVOA model, the SAR is improved by the AVOA in order to optimally cluster and discover cluster centers. AVOA enhances the scope of exploration in SAR. The evaluation of the IKM-SARAVOA model has been performed on six standard datasets from the UCI machine learning database. The fitness function is set based on the sum of squared errors. The results show that the IKM-SARAVOA model has better accuracy compared to SAR and AVOA. IKM-SARAVOA model has achieved fast convergence in a smaller number of iterations.

The knapsack problem is known as a NP-hard problem. The knapsack or rucksack problem consists of determining, given a set of items, each of which has a cost and a value, the number of items included in a collection such that the total cost is less than a given cost and the total value is as large as possible. There is a dynamic programming solution for this problem called the 0-1 knapsack. The 0-1 knapsack problem restricts the number of individual items to zero or one. The shuffled frog-leaping algorithm (SFLA) has long been considered a meta-heuristic algorithm that derives from how frog groups search for food. SFLA can improve computing performance by letting all frogs participate in memetic evolution and access an excellent ability for global search by adding the self-variation behavior to the frog. This study represents an efficient solution for the 0-1 knapsack problem using SFLA. Regarding the parallel nature of most meta-heuristic algorithms, they can be successfully used for speedup. Since it is time-consuming to test all the cases when the problems become larger, Compute Unified Device Architecture (CUDA) is used to implement the solution in parallel. The results of simulating the 0-1 knapsack problem using SFLA on the CUDA platform show that the execution time for a parallel solution decreases as the population of frogs increases. For the 0-1 Knapsack problem, it is 252 times faster than the sequential solution.